package com.rem.se.my;

/**
 * 二分查找
 *
 * @author Rem
 * @date 2023-03-08
 */
public class BinarySearch {


    public static void main(String[] args) {
        int a = 1;
        int[] data = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};

        // System.out.println("普通遍历:" + normal(a, data));

        System.out.println("二分查找次数:" + binary(a, data));

    }

    private static int binary(int num, int[] data) {
        //次数
        int time = 0;

        if (num == data[data.length - 1]) {
            return time;
        }
        //左边下标
        int l = 0;
        //右边下标
        int r = data.length - 1;


        while (data[l] < data[r]) {
            //中间值下标
            int mid = (l + r) >>> 1;
            time++;
            if (num == data[mid]) {
                return time;
            } else if (num > data[mid]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return -1;
    }


    private static int normal(int num, int[] data) {
        int time = 0;
        for (int datum : data) {
            time++;
            if (num == datum) {
                return time;
            }
        }
        return -1;
    }
}
